In general in data communications networks, network devices such as switches, routers, bridges, brouters, etc. constitute nodes of the network and are interconnected by links for communication of data between the nodes. Data communications, or “calls”, between a sending node and a receiving node are routed over paths in the network structure which may involve multiple nodes and links. Information about the network topology is required to determine call paths, and the nature of this topology information, and how it is used, are important factors in the overall efficiency of the system. Network systems, which may comprise a single network or an internetwork, commonly employ some form of hierarchical or multi-layer model whereby nodes at the network layer are grouped in some way, and detailed information about the topology within the group is not available to nodes outside the group. As a simple example, in the case of an internetwork with multiple interconnected networks, detailed information about the topology within a given one of the networks may not be available to the other networks. Thus each individual network can be considered as a group of nodes for which detailed topology information is not available outside the group. A more complex example is provided by PNNI (Private Network-to-Network Interface) networks. The PNNI protocol will be discussed in detail below. Briefly, however, a multi-layer model is employed whereby nodes at the network layer are grouped to form “peer groups”. One node in each peer group is designated “peer group leader” and serves to represent the peer group as a single logical node (a “logical group node” or LGN) in the next layer up of the hierarchy. The nodes in this next layer are similarly grouped into peer groups each of which is represented as a single node in the next layer, and so on. The detailed topology of each peer group is known only to nodes within that peer group. Nodes outside that peer group see the peer group abstracted as a logical group node. A PNNI peer group thus provides another example of a group of nodes (which may themselves be logical group nodes in this case) for which detailed topology information about the group is not available outside the group.
The topology data required for path selection and routing in a network system may include not only details of the layout of nodes and links but also certain “quality of service” parameters. For example, a call to be routed over a network may require a certain bandwidth. In this case, knowledge of the bandwidth of links in the network is required to determine if the call can be connected successfully. To allow such parameters to be taken into account, “costs” can be associated with links and paths in a network. The cost of a link is expressed as an arbitrary value determined as some function of the parameter, eg., bandwidth, about which knowledge is required. Whatever the particular function employed, according to convention it is usual for the cost to be defined such that the lower the cost the better the link. In the case of bandwidth, for example, the cost C of a link may be defined as C=1/bandwidth. A path in a network, involving multiple links, can be measured by a “restrictive cost.” According to the definition of restrictive cost, the weakest link in a path defines the restrictive cost of the path. Thus, when convention is followed such that a higher cost corresponds to a weaker link, the restrictive cost of a path will be determined by the maximum of the costs of the constituent links.
The concept of restrictive cost is useful wherever it is necessary to determine whether a call can traverse a given routing domain for a specified cost. While individual links in a network may have associated costs, the examples of hierarchical systems described above demonstrate that the details of these individual links may not be known throughout the whole network system over which calls are routed. In particular, where there is some group of nodes for which detailed topology information is not available outside the group, it may be necessary to determine whether a call can traverse that group of nodes for a specified cost. In such cases, the necessary information can be provided by a set of restrictive costs, for example in the form of a cost matrix, defining the restrictive cost of paths traversing the group. More specifically, where the group has a number of “border nodes” which are connected by links to nodes outside the group, a set of restrictive costs for the group can include the restrictive costs of the paths between the border nodes. This information can then be used to determine if a given call can be routed across the group for the required cost. There may of course be more than one path between a given pair of border nodes. In this case it is desirable to give the restrictive cost of the best path, ie. that with the lowest restrictive cost. Moreover, costs associated with links and paths can be directional. That is, there may be a particular cost associated with traversing a given link/path in each direction. In effect, therefore, a given link can be considered as a pair of oppositely-directed, unidirectional links each of which has an associated cost, and the cost can be different for the two directions. Such costs are said to be “asymmetric”. To avoid loss of information, it is desirable for such asymmetric costs to be taken into account in deriving the restrictive cost set for a group of nodes, so that the restrictive costs are given for directional paths in both directions between the required nodes. The problem is how to efficiently derive the required set of restrictive costs for a given group of nodes.
The problem is in some ways similar to the class of problems known as “finding all pairs of shortest paths”. Algorithms which address this are discussed by T. H. Cormen, C. E. Leiserson and R. L. Rivest in “Introduction to Algorithms”, The MIT Press, 1989, particular examples being the Floyd-Warshall algorithm and Johnson's algorithm. These algorithms compute optimal paths between all node pairs represented by vertices in a graph. The complexity of these algorithms is no lower than O(neLoge) (with Johnson's algorithm for sparse graphs), and usually O(n3) (Floyd-Warshall algorithm), where n is the number of vertices in the graph and e is the number of edges in the graph.
In order to compute a cost matrix using traditional routing algorithms such as those of Dijkstra, Bellman-Ford or Floyd-Warshall as mentioned above, usually O(n3) steps are needed where n is the number of nodes in the network. As already noted, however, the purpose of these algorithms is to compute a path through a network rather than generate a cost matrix. Our copending European patent application No. 98114966.9, filed Aug. 10, 1998, discloses a method for generating a restrictive cost matrix using a graph coloring technique. This method is also discussed in “Transition Matrix Generation for Complex Node Representations”, I. Iliadis & P. Scotton, IEEE ATM Workshop, Kochi City, Japan, May 27, 1999. This method is based on the minimum spannmg tree growth suggested by the Kruskal and Prim algorithms discussed in the publication of T. H. Cormen mentioned above. The basic principle is to add to a spanning tree (or spanning forest) the safest possible edge at each step. This ensures that, at each step of its growth, the spanning tree (or forest) is minimal. The method employed requires costs to be symmetrical. That is, the cost of a given link is taken to be the same in both directions so that, in effect, only one cost is associated with a given link/path regardless of direction.